package _220310;

import java.util.Scanner;

/**
 * @author ShadowLim
 * @create 2022-03-10-16:30
 */
public class _取球游戏 {

    // 思路： 先手取得最后一个球即输 但是当球剩余数量 == 1 + 1 || 1 + 3 || 1 + 7 || 1 + 8 时，
    //       先手则可以分贝取 1,3,7,8使得最后一个球由后手取得，即胜利
    //       故当剩余球数量为先手的必败状态的球数量 + 1 || + 3 || + 7 || + 8时即为先手的必胜状态

    static int N = 10010;
    static int[] ans = new int[N];

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int[] arr = new int[n];
        for (int i = 1; i < 10000; i++) {
            if (ans[i] == 0) {  // 从1开始 因为1个球 先手为必败状态（用0表示） 接下来可推出必胜状态
                ans[i + 1] = 1;
                ans[i + 3] = 1;
                ans[i + 7] = 1;
                ans[i + 8] = 1;
            }
        }
        for (int i = 0; i < n; i++) {
            arr[i] = scanner.nextInt();
        }
        for (int i = 0; i < n; i++) {
            System.out.println(ans[arr[i]]);
        }
        scanner.close();
    }
}
